package com.msb.datastructure;

import java.util.Comparator;
import java.util.TreeMap;

/**
 * 快速排序
 *
 * @author dataexa
 * @Date 2023/11/21
 */
public class FaseTest {
    public static int[] arr = new int[]{1, 2, 5, 1, 6, 3};

    public static void main(String[] args) {
        quickSort(arr, 0, arr.length - 1);
        CommonUtils.printArray(arr);
    }

    // 快速排序实现
    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            // 获取划分子数组的位置
            int posstion = partition2(arr, L, R);
            // 左边数组调用
            quickSort(arr, L, posstion - 1);
            // 右边数组调用
            quickSort(arr, posstion + 1, R);
        }
    }

    // 单边循环法
    public static int partition(int[] arr, int L, int R) {
        // 选择第一个数为基准元素
        int p = arr[L];
        int mark = L;
        for (int i = L + 1; i < R; i++) {
            if (arr[i] < arr[mark]) {
                mark++;
                int tmp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = tmp;
            }
        }
        //交换基准元素和mark指针的元素
        arr[L] = arr[mark];
        arr[mark] = p;
        return mark;
    }

    // 双边循环法
    public static int partition2(int[] arr, int L, int R) {
        int baseNumber = arr[L];
        int p1 = L;
        int p2 = R;
        while ((L < R) && p1 != p2) {
            while ((p1 < p2) && arr[p2] > baseNumber) {
                p2--;
            }
            while ((p1 < p2) && arr[p1] <= baseNumber) {
                p1++;
            }
            if (p1 < p2) {
                int temp = arr[p2];
                arr[p2] = arr[p1];
                arr[p1] = temp;
            }
        }
        // 重合数和基数交换arr[p1]和arr[L]
        arr[L] = arr[p1];
        arr[p1] = baseNumber;

        return p1;
    }

    public static int partition01(int[] arr, int l, int r) {
        int baseNum = arr[l];
        int p1 = l;
        int p2 = r;
        while ((l < r) && p1 != p2) {
            while ((p1 < p2) && arr[p2] > baseNum) {
                p2--;
            }
            while ((p1 < p2) && arr[p1] <= baseNum) {
                p1++;
            }
            if (p1 < p2) {
                int temp = arr[p1];
                arr[p1] = arr[p2];
                arr[p2] = temp;
            }
        }
        // 交换基数和重合数
        arr[l] = arr[p1];
        arr[p1] = baseNum;
        return p1;
    }
}
